package com.waiting.leetcode;

import java.util.Map;
import java.util.TreeMap;

/**
 * @Description
 * @Author bjweitingting
 * @Date 2019/3/21
 **/
public class ArrayofDoubledPairs954 {

    public static void main(String[] args) {

    }

    public boolean canReorderDoubled(int[] A) {
        //这里用的是treemap
        Map<Integer, Integer> count = new TreeMap<>();
        for (int a : A)
        {
            count.put(a, count.getOrDefault(a, 0) + 1);
        }
        //所以这里是从小到大的一个遍历顺序
        for (int x : count.keySet()) {
            if (count.get(x) == 0) {
                continue;
            }
            int want = x < 0 ? x / 2 : x * 2;
            if (x < 0 && x % 2 != 0 || count.get(x) > count.getOrDefault(want, 0))
                return false;
            count.put(want, count.get(want) - count.get(x));
        }
        return true;
    }
}
